The processing power and capabilities of microprocessors historically increased over time to the point where it became practicable to implement real time computer games using three-dimensional graphics on personal computers and game consoles. Since then there has been a rapid growth in the 3D real-time games market despite the substantial amount of effort required to create each new game, much of this effort stemming from the need to create a realistic and convincing environment in which to immerse the player or players. To meet this need game companies typically employ many artists and level designers as well as skilled programmers. Although a computer game may take years to develop the market is nonetheless very fast paced and a new game may have a lifetime of only a few months during which it is earning significant revenue. There therefore arises a general need to speed up the process of creation of a game, and a further need to increase the longevity of a game's appeal to its players.
An important subset of games within the 3D games arena is the subset of so-called “first person shooter” (FPS) games, typified by the early examples of Doom (Registered Trade Mark) and Quake (Registered Trade Mark). In this type of game the player is represented as a character within the game and the computer or television screen shows the world within the game as it appears to the player's character. In effect the player sees on the screen what his or her character would see with their own eyes in the virtual 3D environment of the game. This creates a strong feeling of immersion in the virtual environment for the game player. Technically such FPS games are different to other games where, for example, the screen presents a view from above and behind the player's character and including the player's character (which might be termed a “third person shooter”). This is because in a first person shooter game the player is generally permitted to manipulate the game controls to view any part of the environment around the player's character whereas in a third person shooter game the view “projected” onto the screen is more restricted.
FIG. 1 shows a screenshot 100 of a first person shooter-type game illustrating the main features of such a game (the screenshot is, in fact, taken from a game constructed using a method according to the invention described below). In FIG. 1 the only part of the player's character which is visible is the character's weapon 102. In the illustrated screenshot the character is looking forwards, but the character may also be turned to look backwards, sideways, up and down. Screen displays 104 indicate game-related data such as ammunition level, armour level, character life, and a score or ranking.
The virtual environment within which the player's character moves is defined by visual geometry onto which colours and textures are mapped. The screenshot of FIG. 1 illustrates a junction between two rooms or halls within the virtual environment. The environment is also provided with lighting effects, although these are not generally implemented using ray tracing but instead rely on a combination of painting on lights, such as lights 106, onto the visual geometry and locally modifying texture, colour and/or intensity in the vicinity of the lights. The game environment usually contains objects, such as armour 108, which may be picked-up or manipulated by the player's character. Also present in the virtual game environment, but invisible to the player, are collision geometry surfaces for determining where and how the player's character is permitted to move. The collision geometry may simply coincide with the visual geometry but, for speed, where the visual geometry is relatively complex it may be approximated by simpler collision geometry, for example replacing a wall with 3D features such as wall 10 in FIG. 1, with a flat wall for the collision geometry.
To simplify the calculations required for rendering the part of the 3D virtual environment viewed by the player's character on the screen the environment may be sub-divided by invisible planes or portals, which can be used for determining which regions of the 3D game environment need to be included in a visible surface determination process. These planes or portals, which are described in more detail later, also facilitate the provision of special effects for regions within the game such as, for example, lighting effects or water effects.
In single-player mode the player generally progresses through a number of game levels, each comprising a separate 3D environment. The player's character generally encounters non-player characters (NPCs) in each level, some of which may be friendly, but most of which are usually hostile and must be killed. Once the player's character has progressed through all the game's levels, the game is over. In other modes a plurality of players' characters are present, optionally with additional non-player characters. In these modes a plurality of players may each be provided with a game controller for a common games console or personal computer, or a number of players using separate consoles or computers may be linked over a network such as local area network (LAN), wide area network (WAN), or the Internet. A number of such multi-player modes may be provided, such as “deathmatch” in which one player's character must kill the characters of all other players not on the same side, and “capture the flag” in which two teams of players each defend a base with a flag which must be captured by the other side to win.
Three-dimensional virtual environment games such as the FPS game outlined above may be run on any general-purpose computer system or on a dedicated computer games console, such consoles generally incorporating specialized hardware to speed-up graphics-related operations. Games for games consoles may be developed on a general-purpose computer system such as a personal computer running Windows (Registered Trade Mark) or Linux (Registered Trade Mark) using cross-compilation software. Players of games on personal computers often upgrade their computer hardware by incorporating a 3D graphics card providing dedicated hardware for speeding-up the type of operations generally encountered when processing 3D graphics. Three-dimensional graphics may implemented by means of a 3D graphics engine providing 3D application program interface (API) calls for controlling the computer's hardware to display three-dimensional graphics either on a visual display unit or, more likely for a games console, on a television. Common 3D graphics languages include OpenGL (from Silicon Graphics, Inc.) and Direct3D (from Microsoft Corporation) (trade marks). Alternatively such graphics may be implemented entirely by proprietary code. A computer game such as an FPS computer game generally comprises data defining the game's environment and operation, and a game engine which operates on the game data to provide the specified game functionality such as NPC artificial intelligence, game physics, and the like, and which makes 3D graphics languages API calls for displaying the game's virtual environment on-screen to the player.
A number of game editors/engines are available in the public domain and can be used to create new games. For example, the editor for the computer game Unreal (trade mark), UnrealEd, is packaged and sold together with the game (more details at http://unreal.epicgames.com). Likewise ID software has released the source code for QE4, their game level editor for creating game virtual environments, as well as Quake II compiling utilities (see, for example www.idsoftware.com, www.quake2.com/qworkshop/features/files.htm and many Quake-related sites), and other game editors/engines have been written based upon these (see, for example, QERadiant at www.qeradiant.com).
The virtual environment of a level in a first person shooter game is defined by data comprising a number of different elements. Geometry data defines the physical (geometrical) appearance of the level and this physical geometry is typically formed from surfaces comprising a plurality of triangles, quadrilaterals, or polygons. Texture data provides images of different types of material which are applied to the level geometry to create a more realistic appearance for the virtual environment of the level. To facilitate the smooth running of the game visibility information is provided to allow the 3D processing engine to only process and display part of the level which is visible on the screen. There are a number of known methods for achieving this and these usually involving splitting-up the geometry and other data into groups so that data in a non-visible group need not be processed.
The characters and other objects moving within a level (either player characters or, in some cases, non-player characters) need information for determining where the character is allowed to move and where the character is not allowed to move within the level's 3D virtual environment. This information is provided by collision data which, since movement calculations are usually very time-consuming, generally comprises a less detailed version of the visible geometry—that is, the collision geometry has the same basic shape as the visual environment geometry but, to save computation time, the collision geometry is constructed from fewer triangles or polygons.
The non-player characters within a game move and function according to artificial intelligence algorithms. To facilitate the movement of NPCs it is often quicker to define NPC route calculation information rather than to rely on ray casting in conjunction with the collision geometry. Thus navigation data is generally provided which allows an NPC to determine how to move from a first position to a second position within the level via a reasonably efficient route. This navigation data may be provided by a set of three-dimensional points and links between the points. This navigation data can then be used for moving NPCs which are invisible to the player's character at predetermined speeds. When an NPC becomes visible it is drawn at the appropriate position and an animation is played to show the NPC's movement. Visible NPC movements and fights generally employ ray casting but, if an NPC wants to move to a position to which it cannot ray cast, again the navigation data may be used. The final significant class of information for a game level is position information, defining where the player's characters start, where weapons and ammunition appear, the location of health and armour points, the location of teams' bases and the like.
The conventional way of creating a level in such a game is to manually create all of the above-described information, for example using a game level editor software package or a commercial 3D design package. However, creating a level in this way typically takes between two and six months of which more than half the time is spent creating the geometry for the game. A significant amount of time is also needed for testing that the visibility, collision, and route calculation information is accurate. If the geometry and other data is not perfect, that is self-consistent and defining a complete, closed environment, the game may not work properly or at all. For example visual artefacts may be left whilst defective collision geometry, such as inconsistent or incomplete collision geometry, can allow a player's character to “fall out” of a game level through an invisible hole. The public domain and proprietary tools for game level editing facilitate the level construction process but the task is nevertheless slow and laborious. It is also difficult for inexperienced game designers to know how to optimize the data for a game level in order that the game runs relatively smoothly and does not run too slowly.
There therefore exists a need for improved methods and apparatus for constructing virtual environments, particularly virtual environments for computer games, such as levels in a first person shooter-type game.